n=997;
m=1000;
q=70;
belt=[|546,283|
567,706|
821,731|
423,498|
548,823|
296,634|
370,195|
246,22|
924,442|
308,628|
280,776|
949,377|
410,374|
393,142|
149,851|
810,136|
551,601|
707,708|
23,176|
885,742|
678,334|
561,776|
889,310|
206,863|
788,996|
886,307|
320,738|
460,780|
597,510|
459,58|
297,3|
193,784|
78,84|
418,904|
306,976|
117,535|
275,180|
393,443|
249,559|
239,248|
946,921|
155,994|
6,987|
458,211|
645,338|
513,993|
57,449|
402,309|
78,746|
66,205|
485,73|
773,387|
234,545|
577,247|
280,139|
686,938|
824,24|
844,545|
719,472|
372,486|
832,936|
883,106|
281,639|
253,485|
836,302|
65,349|
881,342|
192,665|
429,375|
430,748|
26,253|
358,683|
724,204|
786,712|
749,381|
18,763|
533,384|
629,859|
986,193|
706,182|
847,489|
262,312|
479,761|
308,359|
278,660|
90,687|
597,70|
803,657|
186,481|
894,86|
260,727|
952,321|
433,89|
744,821|
512,613|
335,265|
78,903|
95,495|
569,323|
811,833|
42,995|
689,986|
524,766|
360,750|
615,546|
882,801|
32,884|
343,919|
651,406|
515,462|
587,113|
796,775|
554,847|
89,161|
681,140|
237,794|
272,412|
493,552|
367,954|
616,841|
414,489|
26,934|
103,521|
629,368|
755,412|
919,825|
982,781|
168,68|
650,680|
346,746|
800,803|
97,912|
671,320|
338,344|
548,42|
925,589|
313,137|
97,92|
446,17|
860,406|
485,733|
583,472|
706,156|
916,237|
900,777|
229,394|
762,676|
511,93|
987,396|
943,499|
221,142|
253,417|
959,441|
853,34|
957,825|
695,866|
820,367|
992,887|
388,105|
842,196|
70,959|
972,241|
722,119|
399,791|
519,982|
36,626|
898,841|
320,722|
864,504|
425,566|
961,994|
282,871|
65,614|
458,878|
697,974|
738,532|
458,598|
754,493|
336,180|
378,280|
306,839|
433,570|
875,803|
733,301|
57,244|
303,366|
201,277|
386,849|
869,729|
476,849|
994,52|
120,397|
507,958|
201,87|
718,817|
357,722|
982,432|
867,975|
162,478|
238,861|
142,406|
728,949|
30,374|
190,795|
865,766|
610,931|
675,339|
764,277|
623,403|
441,170|
440,628|
99,340|
62,950|
20,391|
638,176|
260,608|
617,939|
97,839|
123,683|
541,286|
232,312|
627,809|
249,875|
154,466|
920,797|
535,567|
983,594|
923,565|
194,364|
861,568|
196,49|
664,463|
45,838|
581,431|
527,171|
187,785|
663,205|
385,627|
173,178|
142,738|
200,491|
189,455|
333,766|
512,607|
362,500|
992,879|
930,799|
348,792|
458,13|
282,513|
287,857|
29,822|
368,276|
826,345|
966,426|
239,776|
385,412|
658,558|
243,624|
344,304|
125,730|
274,962|
647,951|
8,791|
837,704|
379,67|
992,745|
400,520|
192,140|
723,240|
222,750|
918,852|
963,909|
908,495|
292,982|
217,172|
153,819|
629,787|
775,354|
430,895|
18,888|
716,207|
423,648|
19,400|
438,985|
509,969|
330,219|
247,652|
247,382|
353,291|
540,829|
480,602|
538,203|
492,309|
219,319|
573,463|
903,582|
500,497|
490,839|
252,575|
394,365|
473,908|
102,755|
556,135|
960,934|
613,605|
143,94|
40,944|
387,125|
913,795|
476,947|
657,686|
338,87|
997,535|
656,964|
248,322|
861,902|
49,921|
339,347|
144,420|
97,46|
655,865|
408,274|
312,92|
608,627|
929,17|
839,423|
303,609|
903,212|
563,926|
184,737|
924,236|
430,923|
705,13|
447,792|
498,314|
28,717|
173,65|
711,815|
847,812|
338,838|
655,649|
342,894|
844,25|
474,91|
80,967|
133,924|
948,191|
755,324|
307,588|
98,420|
803,115|
545,738|
58,186|
888,714|
27,604|
318,612|
250,943|
691,4|
434,164|
335,830|
732,42|
281,68|
808,234|
662,230|
889,834|
890,721|
789,729|
324,321|
611,264|
485,927|
981,536|
24,475|
145,795|
307,545|
933,231|
644,346|
954,411|
695,843|
494,185|
326,818|
331,420|
550,609|
147,182|
981,510|
917,198|
807,738|
544,271|
207,525|
851,805|
288,244|
318,853|
612,623|
188,691|
62,923|
704,935|
258,145|
631,680|
553,908|
942,536|
400,163|
889,318|
205,948|
373,785|
471,275|
713,406|
275,673|
458,531|
514,450|
920,951|
433,851|
233,968|
464,491|
857,430|
457,521|
289,435|
253,558|
838,466|
587,638|
719,662|
267,543|
839,959|
547,867|
316,251|
959,5|
142,571|
389,349|
930,613|
433,991|
111,41|
522,88|
940,299|
266,997|
319,706|
906,108|
487,210|
74,685|
329,793|
799,59|
703,319|
513,349|
57,318|
374,653|
883,880|
24,676|
71,332|
639,674|
487,810|
211,128|
710,295|
380,262|
774,815|
140,504|
828,442|
400,501|
54,146|
670,937|
158,934|
15,349|
520,187|
74,917|
465,363|
798,912|
28,799|
839,24|
823,564|
940,598|
910,24|
262,534|
742,850|
267,984|
770,146|
110,171|
460,180|
204,12|
725,485|
59,214|
862,68|
351,307|
430,420|
27,542|
749,497|
382,557|
874,579|
749,937|
712,376|
982,408|
992,283|
910,704|
118,961|
525,893|
771,532|
944,268|
578,24|
19,589|
563,458|
726,439|
201,455|
986,60|
112,406|
176,839|
938,776|
596,908|
899,733|
793,500|
910,88|
182,668|
371,965|
954,350|
513,375|
788,753|
307,737|
244,386|
427,136|
677,257|
293,283|
874,422|
761,918|
612,253|
841,427|
751,911|
562,11|
824,598|
188,933|
405,794|
695,186|
591,832|
391,979|
995,100|
733,700|
756,474|
967,487|
76,129|
762,474|
345,638|
842,787|
770,648|
895,971|
541,785|
908,182|
385,388|
37,360|
338,503|
315,215|
309,877|
7,208|
453,366|
384,110|
722,964|
369,24|
824,420|
597,353|
606,233|
398,701|
862,956|
397,386|
371,975|
933,791|
591,356|
297,460|
60,14|
545,729|
176,339|
571,735|
761,402|
124,686|
386,966|
199,695|
437,468|
145,253|
206,853|
489,370|
509,696|
248,114|
294,344|
625,641|
328,587|
420,864|
151,693|
599,600|
704,186|
359,130|
555,668|
166,781|
329,557|
853,982|
926,387|
620,722|
23,678|
833,21|
600,907|
809,707|
870,174|
438,584|
987,721|
840,878|
706,757|
567,591|
758,171|
986,295|
506,705|
21,508|
148,554|
134,521|
980,438|
424,579|
326,60|
15,131|
606,64|
193,803|
768,780|
620,592|
69,434|
884,263|
856,908|
895,51|
87,349|
344,203|
586,736|
767,917|
259,338|
196,824|
400,549|
560,557|
921,480|
444,905|
627,467|
669,321|
857,152|
740,135|
122,676|
933,521|
979,839|
530,940|
629,82|
883,782|
157,402|
827,745|
864,428|
497,421|
602,977|
945,346|
183,986|
892,868|
485,409|
319,882|
346,390|
104,339|
888,55|
279,512|
701,872|
337,655|
723,461|
769,889|
672,675|
814,891|
422,476|
321,636|
396,605|
149,167|
242,303|
610,887|
138,607|
176,551|
435,128|
349,319|
896,460|
27,307|
933,706|
485,349|
300,539|
595,249|
457,363|
679,583|
202,216|
185,763|
983,861|
410,345|
778,260|
300,254|
992,96|
959,87|
252,11|
755,164|
802,236|
89,456|
469,140|
267,699|
169,789|
197,749|
751,740|
488,561|
777,838|
785,151|
698,482|
302,794|
416,722|
83,192|
352,301|
196,825|
141,89|
27,218|
327,119|
637,851|
654,768|
854,618|
153,341|
949,824|
144,355|
401,392|
512,514|
254,746|
638,870|
915,690|
33,498|
688,933|
285,982|
863,468|
107,419|
974,816|
39,267|
216,349|
531,507|
162,182|
225,610|
838,643|
180,867|
612,38|
181,228|
281,386|
752,85|
547,736|
337,515|
651,246|
766,109|
641,37|
711,349|
121,218|
472,265|
979,129|
383,346|
269,438|
702,200|
364,413|
319,630|
116,411|
632,386|
265,517|
590,858|
990,558|
142,238|
497,9|
619,906|
48,711|
716,130|
447,78|
323,319|
747,542|
698,909|
749,11|
646,535|
305,186|
794,613|
234,81|
358,939|
72,980|
486,655|
364,237|
485,992|
933,806|
21,392|
228,29|
787,493|
491,452|
760,583|
56,154|
516,576|
308,959|
340,571|
900,227|
308,633|
75,752|
26,36|
71,97|
309,273|
19,18|
647,886|
24,512|
304,10|
125,953|
527,857|
130,205|
682,870|
346,137|
553,209|
314,829|
523,975|
344,284|
858,987|
638,439|
183,255|
992,193|
780,922|
810,159|
680,603|
585,542|
988,81|
172,82|
514,412|
176,180|
624,101|
563,624|
142,677|
44,345|
848,780|
483,487|
819,451|
654,235|
932,624|
224,735|
709,505|
982,767|
79,869|
130,841|
684,784|
694,269|
759,223|
966,876|
488,295|
179,804|
914,258|
207,470|
528,3|
446,283|
408,419|
813,75|
407,308|
509,731|
753,888|
588,845|
1,151|
915,613|
502,961|
37,659|
77,959|
705,179|
967,731|
574,429|
485,943|
882,269|
779,810|
509,634|
599,87|
281,208|
139,598|
955,425|
317,186|
883,482|
411,297|
12,959|
529,686|
983,290|
721,463|
64,50|
765,825|
622,32|
175,509|
148,897|
271,829|
236,325|
706,772|
476,692|
567,740|
63,435|
165,834|
465,176|
635,689|
226,663|
315,457|
361,60|
61,729|
78,621|
972,44|
402,24|
817,931|
618,312|
245,744|
177,518|
444,5|
268,289|
436,194|
660,349|
366,720|
819,728|
196,303|
344,749|
16,154|
505,906|
187,379|
37,689|
833,692|
261,978|
609,177|
919,261|
433,270|
707,31|
150,362|
520,865|
719,711|
535,445|
500,924|
837,846|
398,899|
87,491|
661,438|
97,847|
607,680|
955,2|
104,526|
805,418|
743,500|
868,412|
752,335|
111,767|
789,415|
901,393|
430,433|
487,320|
814,262|
723,279|
484,214|
739,562|
106,47|
32,181|
318,885|
416,855|
986,989|
516,832|
662,873|
638,537|
441,43|
853,687|
840,928|
751,642|
307,316|
666,172|
254,853|
132,480|
32,711|
138,667|
714,298|
835,825|
489,572|
941,651|
973,683|
141,395|
223,689|
454,59|
968,972|
816,11|
21,94|
640,420|
97,593|
126,790|
607,505|
155,219|
496,819|
306,311|
783,468|
472,342|
344,376|
791,970|
216,741|
223,939|
899,477|
580,370|
213,182|
790,141|
774,256|
398,425|
878,394|
760,734|
482,97|
505,35|
548,57|
796,487|
938,53|
715,680|
386,431|
824,738|
448,743|
520,344|
404,738|
642,264|
267,607|
61,511|
220,870|
838,160|
127,211|
831,71|];
order=[|121,542|
822,359|
962,45|
870,904|
247,693|
469,88|
605,222|
356,738|
878,453|
416,211|
127,837|
168,956|
506,333|
962,856|
692,498|
535,286|
256,346|
422,737|
692,627|
415,511|
468,497|
10,711|
398,621|
915,164|
269,687|
613,342|
180,653|
315,915|
256,558|
17,347|
895,933|
802,413|
490,29|
829,136|
431,219|
863,411|
914,272|
499,231|
62,66|
670,465|
513,257|
576,63|
381,603|
725,12|
834,299|
264,285|
83,23|
362,556|
247,330|
823,497|
123,909|
443,245|
491,702|
32,942|
738,979|
599,728|
236,93|
917,315|
831,773|
205,261|
272,442|
456,864|
716,732|
653,225|
109,207|
947,127|
917,176|
848,25|
849,17|
142,1|];